/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class TreeNode(var `val`: Int) {
       var left: TreeNode? = null
       var right: TreeNode? = null
}
    
class Solution {
    fun maxDepth(root: TreeNode?): Int {
        return getMaxDepth(root,1)
    }

    /**
     * 解法一 递归
     */
    private fun getMaxDepth(root:TreeNode?,deep:Int):Int{
        if(root==null){
            return deep-1;
        }
        return max(getMaxDepth(root?.left,deep+1),getMaxDepth(root?.right,deep+1))
    }

    
}


class Solution {

    /**
     * 解法二 广度优先算法
     */
    fun maxDepth(root: TreeNode?): Int {
        if(root==null){
            return 0;
        }
        var depth = 0;
        val list = mutableListOf(root);


        //将每个节点存到集合，知道
        while(list.isNotEmpty()){ 
            val size = list.size
           (1..size).forEach{
            val lastElement = list.removeLast();
            if(lastElement.left!=null){
             list.add(0,lastElement.left)
            }
 
            if(lastElement.right!=null){
             list.add(0,lastElement.right)
            }
           }
           depth++
        }

        return depth
    }

}

class Solution {

    /**
     * 解法三 深度优先算法
     * 
     * 先处理左节点
     */
    fun maxDepth(root: TreeNode?): Int {
        if(root==null){
            return 0;
        }

        val list = mutableListOf(root)
        val depList = mutableListOf(1)

        var depth = 0
        
        while(list.isNotEmpty()){
            val node = list.removeLast()
            val temp = depList.removeLast()
            depth = max(temp, depth)
            if(node.left!=null){
                list.add(node.left)
                depList.add(temp+1)
            }

            if(node.right!=null){
                list.add(node.right)
                depList.add(temp+1)
            }

        }


        return depth
    }

}